/*
		Aim: C program to implement the python list datatype in c using linked list

*/

#include<stdio.h>
#include<malloc.h>

struct node{
int value;
struct node *next;
};

void menu(void)
{
	printf("\n\t***********************************************************\n");
	printf("\t\n Choose an action to perform on the list :\n");
	printf("1. Display the list elements \n");
	printf("2. Append an element to the list\n");
	printf("3. Extend the list\n");
	printf("4. Insert an element at ith position\n");
	printf("5. Remove an element from the list\n");
	printf("6. Pop an element from the list\n");
	printf("7. Get the index of an element\n");
	printf("8. Get the count of the number of occurence of that element\n");
	printf("9. Sort the list.\n");
	printf("10. Reverse the list.\n");
	printf("\n\t***********************************************************\n");
	printf("Enter your choice :");
}




struct node *add_node(struct node *list, int n)
{
	struct node *new_node;
	new_node = malloc(sizeof(struct node));
	if(new_node==NULL)
	{
		printf("malloc failed\n");
	}
	new_node->value=n;
	new_node->next=list;
	return new_node;
}


void display(struct node*list)
{
	struct node *p;
	printf("\nPrinting your list :\n[");
	for(p=list;p!=NULL;p=p->next)
	{
		printf("%d  ",p->value);
	}
printf("]");
}

struct node *insert(struct node* first, int n, int pos)
{
	struct node *p,*new;
	int i;
	new = malloc(sizeof(struct node));
	if(new==NULL)
	{
		printf("malloc failed\n");
	}
	new->value=n;
	for(p=first,i=1;i<pos;p=p->next,i++);
	new->next=p->next;
	p->next=new;
	return first;	
}

struct node *delete(struct node *list, int n)
{
	struct node *cur, *prev;
	  
	for (cur = list, prev = NULL;
        cur != NULL && cur->value != n;
       	prev = cur, cur = cur->next);
    	
	if (cur == NULL) 
    		return list;             /* n was not found */
 	if (prev == NULL)
		list = list->next;       /* n is in the first node */
  	else
    		prev->next = cur->next;  /* n is in some other node */
  	free(cur);
  	return list;
}       

struct node *sort (struct node *start, int n )
{
	int i, j, k, temp ;
	struct node *p, *q ;
	k = n ;
	for ( i = 0 ; i < n - 1 ; i++, k-- )
	{
		p=start;
		q=p->next;

		for(j=1;j<k;j++)
		{
			if(p->value>q->value)
			{
				temp=p->value;
				p->value=q->value;
				q->value=temp;
			}
				p=p->next;
				q=q->next;
		}
	}
	return start;
}

int count(struct node *first, int n)
{
	struct node *p;
	int i=0;
	for(p=first;p!=NULL;p=p->next)
	{
		if(p->value==n)
			i++;
	}
	return i;
}

struct node* reverse(struct node *list)
{
	struct node *H=NULL,*p;
	while(list!=NULL)
	{
		p=list;
		list=list->next;
		p->next=H;
		H=p;
	}
	return H;
}

int pop(struct node *first, int pos)
{	
	struct node *p;
	int k,i;
	for(i=0,p=first;i<pos;i++,p=p->next)
		k=p->value;
	first=delete(first,k);
	return k;
}

int ind(struct node *first, int n)
{
	struct node *p;
	int i;
	for(i=1,p=first;p->value!=n;i++,p=p->next);
	return i;
}


void main(void)
{
	int i,j,p,k,n,ch,l,size;
	struct node* first=NULL;
	printf("Enter the no. of Elements in the list :\n");
	scanf("%d",&j);
	size=j;
	for(i=0;i<j;i++)
	{
		printf("Enter number %d: ", i+1);
		scanf("%d",&p);
		first=add_node(first,p);
	}
	first=reverse(first);
	display(first);
	char ans='y';
do{
	menu();
	scanf("%d",&ch);	
	
	switch(ch)
	{
		case 1:display(first);
			printf("\nDo u wish to continue <y/n>??\n");
			scanf("%s",&ans);
			break;
		case 2: 
			printf("enter the element to be appended :");
			scanf("%d",&n);
			i++;
			first=reverse(first);
			first=add_node(first,n);
			size++;
			first=reverse(first);
			display(first);
			printf("\nDo u wish to continue <y/n>??\n");
			scanf("%s",&ans);
			break; 
		case 3:
			printf("Enter the no. of elements to be added :\n");
			scanf("%d",&n);
			size+=n;
			first=reverse(first);
			for(l=0;l<n;l++)
			{
				printf("Enter number %d: ", l+i+1);
				scanf("%d",&k);
				first=add_node(first,k);
			}
			i=size;
			first=reverse(first);
			display(first);
			printf("\nDo u wish to continue <y/n>??\n");
			scanf("%s",&ans);
			break;
		case 4:	
			printf("enter the element to be inserted :");
			scanf("%d",&n);
			printf("enter the position :");
			scanf("%d",&k);
			if(k>size)
			{
				printf("Beyond the array size\n");
				printf("\nDo u wish to continue <y/n>??\n");
				scanf("%s",&ans);
				break;
			}
			k--;i++;
			size++;
			first=insert(first,n,k);
			display(first);
			printf("\nDo u wish to continue <y/n>??\n");
			scanf("%s",&ans);
			break;
		case 5:
			printf("enter the element to be removed :");
			scanf("%d",&n);
			first=delete(first,n);
			size--;
			display(first);
			printf("\nDo u wish to continue <y/n>??\n");
			scanf("%s",&ans);
			break;
		case 6: 
			printf("enter the position of the element to be popped :");
			scanf("%d",&n);
			if(n>size)
			{
				printf("Beyond the array size\n");
				printf("\nDo u wish to continue <y/n>??\n");
				scanf("%s",&ans);
				break;
			}
			k=pop(first,n);
			size--;
			printf("element popped out is :%d\n",k);
			printf("\nDo u wish to continue <y/n>??\n");
			scanf("%s",&ans);
			break;
		case 7:
			printf("enter the element to get the index value :");				
			scanf("%d",&n);
			k=ind(first,n);	
			if(k==0)	
				printf("element not found\n");
			else
				printf("element %d found at index : %d\n",n,k);
			printf("\nDo u wish to continue <y/n>??\n");
			scanf("%s",&ans);
			break;
		case 8: 
			printf("enter the element to be counted :");
			scanf("%d",&n);
			k=count(first,n);
			printf("the number of occurences of %d in the list is: %d\n",n,k);
			printf("\nDo u wish to continue <y/n>??\n");
			scanf("%s",&ans);
			break;	
		case 9:
			first=sort(first,size);
			printf("\nyour list has been sorted\n");
			display(first);
			printf("\nDo u wish to continue <y/n>??\n");
			scanf("%s",&ans);
			break;
		case 10:
			first=reverse(first);
			printf("\nyor list has been reversed\n");
			display(first);
			printf("\nDo u wish to continue <y/n>??\n");
			scanf("%s",&ans);
			break;
	}
}while(ans=='y'||ans=='Y');
printf("\nthe program is quiting....\n");
}
	



